1. Field of the Invention
This invention relates to an arrangement optimization problem processing method and an arrangement optimization problem processing apparatus as well as a computer-readable recording medium on which an arrangement optimization problem processing program is recorded, suitable for use, for example, to process a circuit arrangement optimization problem for arranging circuits in an optimum condition on a large scale integrated circuit (LSI), more generally a node arrangement optimization problem (or element arrangement optimization problem) for arranging a plurality of nodes (or elements) in an optimum condition in a two- or more-dimensional space.
2. Description of the Related Art
A node arrangement optimum problem particularly is a problem for arranging (mapping) a plurality of nodes, whose connection relationships are indicated in a system space, in an optimum condition in a generation space, and is called graph mapping problem.
First, connection relationships of a plurality of nodes in a system space are shown in FIG. 22. Referring to FIG. 22, reference symbols 130a to 130h denote fixed nodes whose arrangement in a generation space is determined already, and reference numerals 100 to 102, 110, 111 and 120 to 122 denote non-fixed nodes whose optimum arrangement in the generation space is to be determined. Further, reference numeral 1000 denotes the system space.
In the system space 1000, connection relationships between the plurality of nodes are given as a graph 1001. In the graph 1001, the nodes 130a to 130h, 100 to 102, 110, 111 and 120 to 122 are regarded as vertices, and the connection relationships (indicated by double-sided arrow marks in FIG. 22) between the nodes are regarded as sides between the vertices. It is to be noted that the coupling strength between each two nodes is indicated by the thickness of the pertaining double-sided arrow mark.
When it is tried to arrange the plurality of non-fixed nodes 100 to 102, 110, 111 and 120 to 122 in the generation space, the following constraints are taken into consideration:
i) Magnitudes of the Nodes in the Generation Space
Each of the nodes has a peculiar magnitude.
ii) Connection Relationships of a Plurality of Nodes in the System Space
Connection relationships between a plurality of nodes are given as a graph 1001. Further, a certain node is connected to a fixed node.
Then, by executing, for example, a genetic algorithm as an algorithm for solution to an optimization problem while the constraints described above are taken into consideration, optimum arrangement of the plurality of nodes 100 to 102, 110, 111 and 120 to 122 in the generation space is determined, and based on the determination, the plurality of nodes 100 to 102, 110, 111 and 120 to 122 are arranged in the generation space.
It is to be noted that a genetic algorithm is an algorithm devised based on a concept of the principle of evolution of organisms. In the genetic algorithm, candidates for a solution to an arrangement optimization problem are represented as chromosomes which are arrangements of genes, and various genetic operations (selection/self-reproduction, mutation and crossover) are performed for the chromosomes to update the generation to determine an optimum solution given as a gene arrangement of a chromosome having a high fitness value (that is, an optimum arrangement of the plurality of nodes 100 to 102, 110, 111 and 120 to 122 in the generation space).
An example of a result of arrangement of the plurality of nodes 100 to 102, 110, 111 and 120 to 122 in the generation space is shown in FIG. 23.
Generally, the generation space is a two- or more-dimensional space, and each node may have an arbitrary shape in accordance with the dimensions of the generation space. Referring to FIG. 23, the generation space 2000 shown has a rectangular shape, and the nodes (non-fixed nodes 100 to 102, 110, 111 and 120 to 122 shown in FIG. 22) have shapes defined to rectangles and arranged in the generation space 2000. It is to be noted that, also in FIG. 23, reference symbols 130a to 130h denote fixed nodes whose arrangement in the generation space is determined already.
By executing a genetic algorithm to process a node arrangement optimization problem in this manner, an optimum arrangement of a plurality of nodes in an actual space in which only connection relationships are indicated is obtained.
In regard to, for example, an LSI mentioned above, if an optimum arrangement of circuits on the LSI can be determined, then not only minimization of the LSI can be achieved, but also minimization in length of wiring lines for interconnecting the circuits can be achieved to augment the wiring facility. Consequently, higher speed processing in the LSI can be achieved.
However, there is a subject to be solved in that, where a genetic algorithm is employed as an optimization problem solution algorithm which is used to process a node arrangement optimization problem, when the scale of the optimization problem is large, that is, when the number of nodes whose optimum arrangement is to be determined is very large, very much time is required to determine an optimum arrangement of the nodes.
It is an object of the present invention to provide an arrangement optimization problem processing method and apparatus by which an optimum arrangement of a plurality of nodes can be determined at a high speed even where a node arrangement optimization problem having a large problem scale is to be processed and a computer-readable recording medium on which an arrangement optimization problem processing program for causing a computer to operate to process a node arrangement optimization problem is recorded.
In order to attain the object described above, according to an aspect of the present invention, there is provided an arrangement optimization problem processing method for arranging a plurality of nodes, whose connection relationships are indicated in a system space, in a generation space, comprising a hyper node formation step of grouping the plurality of nodes to form a plurality of hyper nodes each formed from a set of nodes, a hyper node arrangement step of executing an optimization problem solution algorithm to determine solutions to a problem of arrangement of the plurality of hyper nodes formed by the hyper node formation step in the generation space and arranging the plurality of hyper nodes in the generation space based on one of the determined solutions, and a node optimum arrangement step of executing the optimization problem solution algorithm taking arrangement relationships of the plurality of hyper nodes obtained by the hyper node arrangement step into consideration to determine a solution to a problem of arrangement of the plurality of nodes in an optimum condition in the generation space and arranging the plurality of nodes in the generation space based on the determined solution.
The hyper node arrangement step may arrange the plurality of hyper nodes in the generation space taking a constraint in arrangement of the hyper nodes into consideration.
Further, the arrangement optimization problem processing method may be constructed such that each of the hyper nodes includes a plurality of sub hyper nodes each formed from a partial set of a plurality of nodes which form the hyper node, and the arrangement optimization problem processing method further comprise a constraint search step of determining the constraint to the hyper node based on the constraint to the sub hyper nodes.
The hyper node arrangement step may execute a genetic algorithm as the optimization problem solution algorithm to determine solutions to the problem of arrangement of the plurality of hyper nodes formed by the hyper node formation step in the generation space and arrange the plurality of hyper nodes in the generation space based on one of the determined solutions.
The hyper node arrangement step may arrange the plurality of hyper nodes in the generation space based on an optimum one of the determined solutions or may arrange the plurality of hyper nodes in the generation space based on one of the determined solutions other than the optimum solution.
Where the generation space is a two-dimensional space, the hyper node arrangement step and the node optimum arrangement step may define shapes of the hyper nodes and the nodes as two-dimensional shapes and arrange the hyper nodes and the nodes in the generation space, respectively.
Where the generation space has a rectangular shape, when the hyper node arrangement step and the node optical arrangement step define shapes of the hyper nodes and the nodes to rectangles and arrange the hyper nodes and the nodes in the generation space, respectively, the hyper node arrangement step and the node optimum arrangement step may represent the hyper nodes and the nodes as genes composed of information regarding center coordinates of the rectangles and information regarding aspect ratios of the rectangles and execute the genetic algorithm using chromosomes composed of arrangements of the genes as solution candidates to the problem of arrangement of the plurality of hyper nodes and the plurality of nodes in the generation space, respectively.
When the genetic algorithm is executed, pasting crossover wherein information regarding the center coordinates of the rectangle of one of the genes which compose one of the chromosomes and information regarding the aspect ratio of the rectangle are replaced with the center coordinate information and the aspect ratio information, respectively, of a corresponding one of the genes which compose another one of the chromosomes can be performed as a genetic operation for the chromosomes.
When the genetic algorithm is executed, pasting crossover wherein information regarding the center coordinates of the rectangle of one of the genes which compose one of the chromosomes is replaced with the center coordinate information of a corresponding one of the genes which compose another one of the chromosomes may be performed as a genetic operation for the chromosomes.
In this instance, the pasting crossover may be based on a weighted average of the information regarding the center coordinates of the rectangles.
Further, when the genetic algorithm is executed, pasting crossover wherein information regarding the aspect ratio of the rectangle of one of the genes which compose one of the chromosomes is replaced with the aspect ratio information of a corresponding one of the genes which compose another one of the chromosomes may be performed as a genetic operation for the chromosomes.
In this instance, the pasting crossover may be based on a weighted average of the information regarding the aspect ratios of the rectangles.
When the genetic algorithm is executed, mutation wherein the information regarding the aspect ratio of the rectangle of the gene which composes the chromosome is varied may be performed as a genetic operation for the chromosome.
In this instance, the mutation may increase or decrease the information regarding the aspect ratio of the rectangle at a fixed ratio.
Further, it may be stochastically determined whether the information regarding the aspect ratio of the rectangle should be increased or decreased in the fixed ratio by the mutation.
When the genetic algorithm is executed, mutation wherein the information regarding the center coordinates of the rectangle of the gene which composes the chromosome is varied may be performed as a genetic operation for the chromosome.
In this instance, the mutation may add a stochastically selected value to the information regarding the center coordinates of the rectangle to vary the information regarding the center coordinates of the rectangle.
When the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome may be calculated taking a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes arranged in the generation space into consideration.
As an alternative, when the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome may be calculated taking a sum total of areas of overlapping portions of the plurality of hyper nodes arranged in the generation space into consideration.
As another alternative, when the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome may be calculated taking a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes arranged in the generation space and a sum total of areas of overlapping portions of the plurality of hyper nodes into consideration.
The calculation of the fitness value may be performed by performing weighted calculation for either one of a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes and a sum total of areas of overlapping portions of the plurality of hyper nodes.
When the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome may be calculated taking a sum total of areas of gap portions among the plurality of hyper nodes arranged in the generation space into consideration.
As an alternative, when the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome may be calculated taking a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes arranged in the generation space and a sum total of areas of gap portions among the plurality of hyper nodes into consideration.
The calculation of the fitness value may be performed by performing weighted calculation for either one of a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes and a sum total of areas of gap portions among the plurality of hyper nodes.
Accordingly, with the arrangement optimization problem processing method described above, since hyper nodes formed by grouping a plurality of nodes are arranged in a space and the plurality of nodes are arranged in the space taking arrangement relationships of the hyper nodes, an advantage is exhibited in that, also when it is tried to process a node arrangement optimization problem having a large problem scale, an optimum arrangement of the plurality of nodes can be determined at a high speed.
According to another aspect of the present invention, there is provided an arrangement optimization problem processing method for arranging a plurality of elements in a two- or more-dimensional space, comprising a hyper element formation step of grouping the plurality of elements to form a plurality of hyper elements each formed from a set of elements, a hyper element arrangement step of executing an optimization problem solution algorithm to determine solutions to a problem of arrangement of the plurality of hyper elements formed by the hyper element formation step in the generation space and arranging the plurality of hyper elements in the generation space based on one of the determined solutions, and an element optimum arrangement step of executing another optimization problem solution algorithm taking arrangement relationships of the plurality of hyper elements obtained by the hyper element arrangement step into consideration to determine a solution to a problem of arrangement of the plurality of elements in an optimum condition in the generation space and arranging the plurality of elements in the generation space based on the determined solution.
Also with the arrangement optimization problem processing method, an advantage is exhibited in that, also when it is tried to process an element arrangement optimization problem having a large problem scale, an optimum arrangement of a plurality of elements can be determined at a high speed.
According to a further aspect of the present invention, there is provided an arrangement optimization problem processing apparatus for processing a node arrangement optimization problem to arrange a plurality of nodes, whose connection relationships are indicated in a system space, in an optimum condition in a generation space, comprising a hyper node formation section for grouping the plurality of nodes to form a plurality of hyper nodes each formed from a set of nodes, a hyper node arrangement section for executing an optimization problem solution algorithm to determine solutions to a problem of arrangement of the plurality of hyper nodes formed by the hyper node formation section in the generation space and arranging the plurality of hyper nodes in the generation space based on one of the determined solutions, and a node optimum arrangement section for executing the optimization problem solution algorithm taking arrangement relationships of the plurality of hyper nodes obtained by the hyper node arrangement section into consideration to determine a solution to a problem of arrangement of the plurality of nodes in an optimum condition in the generation space and arranging the plurality of nodes in the generation space based on the determined solution.
According to a still further aspect of the present invention, there is provided a computer-readable recording medium storing an arrangement optimization problem processing program for causing a computer to process a node arrangement optimization problem to arrange a plurality of nodes, whose connection relationships are indicated in a system space, in an optimum condition in a generation space, the arrangement optimization problem processing program causing the computer to function as a hyper node formation section for grouping the plurality of nodes to form a plurality of hyper nodes each formed from a set of nodes, a hyper node arrangement section for executing an optimization problem solution algorithm to determine solutions to a problem of arrangement of the plurality of hyper nodes formed by the hyper node formation section in the generation space and arranging the plurality of hyper nodes in the generation space based on one of the determined solutions, and a node optimum arrangement section for executing the optimization problem solution algorithm taking arrangement relationships of the plurality of hyper nodes obtained by the hyper node arrangement section into consideration to determine a solution to a problem of arrangement of the plurality of nodes in an optimum condition in the generation space and arranging the plurality of nodes in the generation space based on the determined solution.
Also with the arrangement optimization problem processing apparatus and the computer-readable recording medium, an advantage is exhibited in that, also when it is tried to process a node arrangement optimization problem having a large problem scale, an optimum arrangement of a plurality of nodes can be determined at a high speed.